// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]`是数组 `[0,3,1,6,2,2,7]` 的子序列。
// 子序列，由数组派生而来，删除数组中的元素而不改变其余元素的顺序
// 1. dp数组含义，`dp[i]`,表示i之前的以`nums[i]`结尾的最长递增子序列的长度
// 2. 状态转移方程
// ```js
// if(nums[i] > nums[j]) {
//     dp[i] = Math.max(dp[i], dp[j] + 1)
// }
// ```
// 3. `dp[i]`的初始化，对于每个i，起始大小都是1
// 4. 确定遍历顺序，`dp[i]`是由从0到i-1的各个位置的最长递增子序列推导而来，所以一定是从前往后遍历
// 5. 举例推导
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
function lengthOfLIS(nums) {
    let dp = new Array(nums.length).fill(1)
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }            
        }        
    }
    return Math.max(...dp)
}

let nums = [10,9,2,5,3,7,101,18]
console.log(lengthOfLIS(nums))

function getSequence (arr) {
    const p = arr.slice()
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {
      const arrI = arr[i]
      // 排除等于 0 的情况
      if (arrI !== 0) {
        j = result[result.length - 1]
        // 与最后一项进行比较
        if (arr[j] < arrI) {
          // 存储在 result 更新前的最后一个索引的值
          p[i] = j
          result.push(i)
          continue
        }
        u = 0
        v = result.length - 1
        // 二分搜索，查找比 arrI 小的节点，更新 result 的值
        while (u < v) {
          // 取整得到当前位置
          c = ((u + v) / 2) | 0
          if (arr[result[c]] < arrI) {
            u = c + 1
          }
          else {
            v = c
          }
        }
        if (arrI < arr[result[u]]) {
          if (u > 0) {
            // 正确的结果
            p[i] = result[u - 1]
          }
          // 有可能替换会导致结果不正确，需要一个新数组 p 记录正确的结果
          result[u] = i
        }
      }
    }
    u = result.length
    v = result[u - 1]
  
    // 回溯数组 p，找到最终的索引
    while (u-- > 0) {
      result[u] = v
      v = p[v]
    }
    return result
  }

  
  let num2 = [1, 4, 5, 2, 8, 7, 6, 0]
  console.log(getSequence(nums))